1. Field of the Invention
The present invention relates to public key cryptography using an algebraic surface.
2. Description of the Related Art
In recent years, as public key cryptography that may not be possibly efficiently decrypted by a quantum computer and can be processed at a high speed even in a low-power environment, public key cryptography using an algebraic surface has been suggested (see, e.g., K. Akiyama, Y. Goto, “An improvement of the algebraic surface public-key cryptosystem”, Symposium on Cryptography and Information Security 2008, IF1-2 (2008)), hereinafter referred to as AG08.
According to the public key cryptography using an algebraic surface, assuming that a private key is two sections associated with an algebraic surface X(x,y,t) and a public key is the algebraic surface X(x,y,t), encryption processing that generates two encrypted texts Fi(x,y,t)=E(m,si,ri,f,X) (i=1,2) from a plaintext polynomial m(x,y,t) is executed based on processing of embedding a plaintext m in the plaintext polynomial m(x,y,t), processing of randomly generating a factor polynomial f(x,y,t), polynomial generation processing of generating a set of two random polynomials si(x,y,t)ri(x,y,t) (i=1,2) having three variables x, y, and t, and processing of performing addition or subtraction with respect to the set of respective polynomials si(x,y,t)ri(x,y,t) (i=1,2) and a definition expression X(x,y,t).
Further, in decryption processing, a section D:(x,y,t)=(ux(t),uy(t),t) as the private key is assigned to two encrypted texts F1(x,y,t) and F2(x,y,t) to obtain respective one-variable polynomials hi(t) and h2(t), a result obtained by subtracting these polynomials is factorized, and a factor having deg f(ux(t),uy(t),t) as a degree is extracted from a result of this factorization. This factor may not be necessarily uniquely extracted. However, when a correct factor polynomial f(ux(t),uy(t),t) can be extracted, dividing one of the one-variable polynomials h1(t) and h2(t) by the factor polynomial f(ux(t),uy(t),t) enables extracting a plaintext polynomial candidate m(ux(t),uy(t),t) that is correct as a residue, thereby restoring the correct plaintext m.
On the other hand, when a factor that is not the factor polynomial f(ux(t),uy(t),t) is extracted, a wrong plaintext m′ is restored by the same arithmetic operation, and an error detecting code or the like previously embedded in the plaintext can be used to find the error.
However, the above-described public key cryptography using an algebraic surface usually has no problem, but realizing the efficiency of entire processing thereof is demanded according to the examination conducted by the present inventor.
For example, in the decryption processing, a major part of a processing time is used for factorization processing and factor extraction processing of extracting a factor having deg f(ux(t),uy(t),t) as a degree from a result of the factorization. In particular, the number of combinations in the factor extraction processing may become tremendous depending on a result of the factorization, whereby the decryption processing time considerably differs. Therefore, in the public key cryptography using an algebraic surface, reducing a burden on the factorization processing and the factor extraction processing that take the major part of the decryption processing time and realizing the efficiency of the entire processing have been demanded.
Moreover, in the decryption processing, an arithmetic processing performed to create two encrypted texts is constituted of 4 times of multiplication and 4 times of addition. Additionally, in the decryption processing, the polynomials h1(t) and h2(t) after the section assignment must be subtracted, and a result of the subtraction must be factorized. Here, in the encryption processing or the decryption processing, reducing a burden on at least one arithmetic processing is desirable.
As explained above, according to the examination performed by the present inventor, in the public key cryptography using an algebraic surface, realizing the efficiency of the entire processing is demanded by reducing the burden on the arithmetic processing in the encryption processing or the decryption processing.